from typing import Counter, List


class Solution:

    """
    方法： findAnagrams

    逻辑: 使用定长滑动窗口，统计字符串s中所有与字符串p的字母出现次数相同的子串的起始索引。

    Args:
        s (str): 输入字符串。
        p (str): 目标字符串，用于比较字母出现次数。

    Returns:
        List[int]: 返回所有符合条件的子串的起始索引。

    Time:  
        O(n), 其中n是字符串s的长度。

    Space:  
        O(1), 固定大小的数组用于统计字母出现次数。
    """
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        cnt_p = Counter(p) #统计字符串p中每个字母出现次数
        cnt_s = Counter() #统计 s 的长为 len(p) 的子串 s' 的每种字母的出现次数
        for right, c in enumerate(s):
            cnt_s[c] += 1
            left = right - len(p) + 1
            if left < 0: # 窗口长度不足 len(p)
                continue
            if cnt_s == cnt_p: # s' 和 p 的每种字母的出现次数都相同
                ans.append(left) # s' 左端点下标加入答案
            cnt_s[s[left]] -= 1 # 左端点字母离开窗口
        return ans
    
    """
    方法： findAnagrams1

    逻辑: 使用不定长滑动窗口，统计字符串s中所有与字符串p的字母出现次数相同的子串的起始索引。

    Args:
        s (str): 输入字符串。
        p (str): 目标字符串，用于比较字母出现次数。

    Returns:
        List[int]: 返回所有符合条件的子串的起始索引。

    Time:  
        O(n), 其中n是字符串s的长度。

    Space:  
        O(1), 固定大小的数组用于统计字母出现次数。
    """
    def findAnagrams1(self, s: str, p: str) -> List[int]:
        ans = []
        cnt = Counter(p) # 统计 p 的每种字母的出现次数
        left = 0
        for right, c in enumerate(s):
            cnt[c] -= 1
            while cnt[c] < 0: # 字母 c 太多了
                cnt[s[left]] += 1 # 左端点字母离开窗口
                left += 1
            if right - left + 1 == len(p): # s' 和 p 的每种字母的出现次数都相同
                ans.append(left) # s' 左端点下标加入答案
        return ans

        